package net.cloudsun.tree.orderbinary;

import net.cloudsun.tree.binary.BinaryNode;

/**
 * @author Ryan
 * @since
 */
public class OrderBinaryNode<T extends Comparable<T>> extends BinaryNode<T> {
    public OrderBinaryNode(T t) {
        super(t);
    }

    @Override
    public void add(BinaryNode<T> newNode) {
        innerAdd((OrderBinaryNode<T>)newNode);
    }

    /**
     * 内部添加方法
     * @param newNode
     * @return
     */
    protected OrderBinaryNode<T> innerAdd(OrderBinaryNode<T> newNode) {
        OrderBinaryNode<T> node = this;
        T t = newNode.value;
        while (node != null) {
            if (t.compareTo(node.getValue()) > 0) {
                // 如果right == null
                if (node.getRight() == null) {
                    node.setRight(newNode);
                    return node;
                }
                node = node.getRight();
            } else if (t.compareTo(node.getValue()) < 0) {
                if (node.getLeft() == null) {
                    node.setLeft(newNode);
                    return node;
                }
                node = node.getLeft();
            } else {
                throw new DuplicateKeyException(t);
            }
        }
        return null;
    }

    public OrderBinaryNode<T> findNode(T t) {
        OrderBinaryNode<T> node = this;
        while (node != null) {
            if (t.compareTo(node.getValue()) > 0) {
                // 如果right == null
                if (node.getRight() == null) {
                    return null;
                }
                node = node.getRight();
            } else if (t.compareTo(node.getValue()) < 0) {
                if (node.getLeft() == null) {
                    return null;
                }
                node = node.getLeft();
            } else {
                return node;
            }
        }
        return null;
    }


    @Override
    public OrderBinaryNode<T> getLeft() {
        return (OrderBinaryNode<T>) super.getLeft();
    }

    @Override
    public OrderBinaryNode<T> getRight() {
        return (OrderBinaryNode<T>) super.getRight();
    }

    /**
     * 左旋，这只能是排序树的左旋
     *   5       6
     *  3 6->   5 7
     * 2 4 7   3
     *        2 4
     * 3 2 4 这个是个整体
     * 可以忽略为
     *  5       7
     * 3 7  -> 5 8
     *  6 8   3 6
     * this的三个属性都变了
     * this.value
     * this.left
     * this.right
     * 记录一次bug
     * 左旋前
     *  1
     * ┌┴┐
     * 0 3
     *  ┌┴┐
     *  2 4
     *    └┐
     *     5
     *
     * 左旋后
     *     3
     *    ┌┴
     *    1
     *   ┌┴┐
     *   0 5
     */
    protected void leftRotate() {
        final BinaryNode<T> originalLeft = this.getLeft();
        final BinaryNode<T> originalRight = this.getRight();
        final T originalValue = this.value;
        if (originalRight != null) {
            this.value = originalRight.getValue();
            this.setRight(originalRight.getRight());
            this.setLeft(originalRight);

            originalRight.setRight(originalRight.getLeft());
            originalRight.setLeft(originalLeft);
            originalRight.setValue(originalValue);
        }
    }

    /**
     * 右旋，这只能是排序树的右旋
     *   1     2
     *  2 5-> 3 1
     * 3 4     4 5
     * this的三个属性都变了
     * this.value
     * this.left
     * this.right
     */
    protected void rightRotate() {
        final BinaryNode<T> originalLeft = this.getLeft();
        final BinaryNode<T> originalRight = this.getRight();
        final T originalValue = this.value;

        this.value = originalLeft == null ? null : originalLeft.getValue();
        this.setRight(originalLeft);
        this.setLeft(originalLeft == null ? null : originalLeft.getLeft());

        if (originalLeft != null) {
            originalLeft.setLeft(originalLeft.getRight());
            originalLeft.setRight(originalRight);
            originalLeft.setValue(originalValue);
        }
    }

    public void delete() {
        innerDelete();
    }

    protected OrderBinaryNode<T> innerDelete() {
        // 排序树节点，删除自己之后还是个排序树。
        // 这是自己不空的情况
        // 分两种情况
        final OrderBinaryNode<T> replacement = getReplacement();
        this.value = replacement.value;

        if (getLeft() == replacement) {
            // 这是最大值,删除了自己
            setLeft(replacement.getLeft());
        } else if (getRight() == replacement) {
            // 修复bug
            setRight(replacement.getRight());
        }
        replacement.parent.removeChild(replacement);

        return replacement;

    }

    public OrderBinaryNode<T> getReplacement() {
        if (getLeft() != null) {
            // 左节点找出最大值
            /*
             *    3
             *   /
             *  2
             * /
             * 1
             *
             */
            OrderBinaryNode<T> node = this.getLeft();
            while (node.getRight() != null) {
                node = node.getRight();
            }
            return node;
        } else if (getRight() != null) {
            // 右节点找出最小值
            /*
             *
             * 4B
             * └┐
             *  5B
             *  └┐
             *   7R
             *
             */
            OrderBinaryNode<T> node = this.getRight();
            while (node.getLeft() != null) {
                node = node.getLeft();
            }
            return node;
        } else {
            return null;
        }
    }
}
